COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00006 ENDMK
C⊗;
\rm

\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm 162B03.tex[v1,rwf] \today\hfill}

\vskip .5in

\noindent
{\bf Algorithmic Entropy}

A problem has $N$ different possible results, which we will represent as the
numbers $1$ to $N$.  Result $j$ has probability $q↓j$.  The {\sl entropy} of
the problem is $E=-\sum↓jq↓j\lg q↓j$.  This is non-negative, and is 0 only if
all the $q↓j$ but one are 0, i.e. the problem is solved.

A test that can be made in a program has $M$ different outcomes, which we will
represent as the numbers from $1$ to $M$.  Outcome $i$ has probability $r↓i$.
The {\sl information} of the test is $I=-\sum r↓i\lg r↓i$.  This is non-negative
and is 0 only if all the $q↓j$, but one are 0, i.e. one outcome is certain.  For a
given number of outcomes, information is maximized by $r↓i=1/M$; then $I=\lg M$.
Given a problem and a test, let $p↓{ij}$ be the probabilty that the test outcome
is $i$ and the problem result is $j$.  Then $q↓j=\sum↓ip↓{ij}$, 
$r↓{i}=\sum↓jp↓{ij}$.
If we make the test and get outcome $i$, the conditional probability of result
$j$ is $p↓{ij}/\sum↓jp↓{ij}=p↓{ij}/r↓i$.  This gives a new entropy
$-\sum↓j(p↓{ij}/r↓i)\lg ({p↓{ij}/r↓i})$.  The expected value of the new entropy is
$$\eqalign{\sum↓ir↓i\left( -\sum↓j({p↓{ij}/r↓i})\lg ({p↓{ij}/r↓i})\right)
&=-\sum↓{i,j}p↓{ij}\lg({p↓{ij}/r↓i})\cr
&=-\sum↓{i,j}p↓{ij}\lg p↓{ij}+\sum↓{i,j}p↓{ij}\lg r↓i\cr
&=-\sum↓{i,j}p↓{ij}\lg p↓{ij}+\sum↓{i,j}r↓i\lg r↓i\cr
&=-\sum↓{i,j}p↓{ij}\lg p↓{ij}-I\cr}$$

We can prove that
$-\sum↓{ij}p↓{ij}\lg p↓{ij}≥-\sum q↓j\lg q↓j,$
with equality only if for each $j$ there is a $k$ with $p↓{kj}=q↓j$, and
$p↓{ij}=0$ for $i≠j$.  Then we conclude: {\bf A test, on the average,
reduces the problem entropy by at most its information.  To achieve even this
much reduction the test outcome must be a function of the problem result.}

Proof that $-\sum↓{ij}p↓{ij}\lg p↓{ij}≥-\sum q↓j\lg q↓j$.  The inequality can be
shown for each $j$ separately.  Let $\sum↓ip↓i=q$, $0≤p↓i$, $q≤1$.  We want to show
$-\sum↓ip↓i\lg p↓i≥-q\lg q$, or $-\sum↓i{{p↓i}\over q}\lg p↓i≥-\lg q$, or
$-\sum↓i{{p↓i}\over q}\lg\left( {{p↓i}\over q}\right)≥0$.
Since $0≤p↓i/q≤1$, this is true term by term, with equality only if
$p↓i/q=0$, so that $p↓i=0$, or if $\lg (p↓i/q)=0$, so that $p↓i=q$.
\vfill \end